// @algorithm @lc id=1194 lang=cpp 
// @title path-in-zigzag-labelled-binary-tree


#define print(...)
// @test(14)=[1,3,4,14]
// @test(26)=[1,2,6,10,26]
class Solution {
public:
    vector<int> pathInZigZagTree(int label) {
        int d = 1;
        while(d <= label) d <<= 1;
        d = __builtin_ctz(d);
        vector<int> ans(d);
        for(--d; ans[d]=label,0<d; d--){
            print("label=", label, ", d=", d, ", ans=", ans, "\n")
            label = d%2 ? ((1<<d)*3-1-label)>>1 : (1<<(d-1))*3-1-(label>>1);
        }
        print("label=", label, ", d=", d, ", ans=", ans, "\n")
        return ans;
    }
};